Backtracking এর প্রয়োগ: Sudoku Solver, Hamiltonian Path
Backtracking একটি জনপ্রিয় সমস্যা সমাধানের কৌশল, যা পরীক্ষার মাধ্যমে সঠিক সমাধান খোঁজার জন্য ব্যবহৃত হয়। এটি একটি ব্রুট ফোর্স পদ্ধতি, যা সমাধানের জন্য সম্ভাব্য সমস্ত বিকল্প পরীক্ষা করে এবং যদি একটি বিকল্প ভুল হয়, তবে সেগুলিকে বাদ দিয়ে পরবর্তী বিকল্পগুলো পরীক্ষা করে। এটি সাধারণত সমস্যা সমাধানে রিকার্সন বা স্ট্যাক ব্যবহার করে।
এখানে Backtracking এর দুটি জনপ্রিয় প্রয়োগ Sudoku Solver এবং Hamiltonian Path নিয়ে আলোচনা করা হবে।
1. Sudoku Solver - Backtracking
Sudoku একটি ক্লাসিক্যাল পাজল যেখানে একটি 9x9 গ্রিডে কিছু সংখ্যা দেওয়া থাকে এবং বাকী স্থানগুলোর সংখ্যা সম্পূর্ণ করতে হবে। সংখ্যাগুলি 1 থেকে 9 পর্যন্ত হতে হবে এবং প্রতিটি সারি, কলাম, এবং 3x3 গ্রিডে কোনো সংখ্যার পুনরাবৃত্তি থাকতে পারবে না।
Sudoku Solver - Backtracking ইমপ্লিমেন্টেশন (সি প্রোগ্রামিং):
#include <stdio.h>
#include <stdbool.h>
#define N 9
// Check if placing num in grid[row][col] is valid
bool isValid(int grid[N][N], int row, int col, int num) {
// Check if num is not repeated in row
for (int i = 0; i < N; i++) {
if (grid[row][i] == num) return false;
}
// Check if num is not repeated in column
for (int i = 0; i < N; i++) {
if (grid[i][col] == num) return false;
}
// Check if num is not repeated in the 3x3 grid
int startRow = row - row % 3, startCol = col - col % 3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (grid[i + startRow][j + startCol] == num) return false;
}
}
return true;
}
// Function to solve the Sudoku puzzle using backtracking
bool solveSudoku(int grid[N][N]) {
int row, col;
// Find the next empty cell
bool emptyFound = false;
for (row = 0; row < N; row++) {
for (col = 0; col < N; col++) {
if (grid[row][col] == 0) {
emptyFound = true;
break;
}
}
if (emptyFound) break;
}
// If no empty cell is found, puzzle is solved
if (!emptyFound) return true;
// Try placing numbers 1 to 9
for (int num = 1; num <= 9; num++) {
if (isValid(grid, row, col, num)) {
grid[row][col] = num;
// Recursively attempt to solve the rest of the grid
if (solveSudoku(grid)) {
return true;
}
// If placing num didn't work, backtrack
grid[row][col] = 0;
}
}
return false; // Trigger backtracking
}
// Function to print the Sudoku grid
void printGrid(int grid[N][N]) {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
printf("%d ", grid[i][j]);
}
printf("\n");
}
}
int main() {
// A Sudoku puzzle with 0's representing empty cells
int grid[N][N] = {
{5, 3, 0, 0, 7, 0, 0, 0, 0},
{6, 0, 0, 1, 9, 5, 0, 0, 0},
{0, 9, 8, 0, 0, 0, 0, 6, 0},
{8, 0, 0, 0, 6, 0, 0, 0, 3},
{4, 0, 0, 8, 0, 3, 0, 0, 1},
{7, 0, 0, 0, 2, 0, 0, 0, 6},
{0, 6, 0, 0, 0, 0, 2, 8, 0},
{0, 0, 0, 4, 1, 9, 0, 0, 5},
{0, 0, 0, 0, 8, 0, 0, 7, 9}
};
if (solveSudoku(grid)) {
printf("Solved Sudoku:\n");
printGrid(grid);
} else {
printf("No solution exists\n");
}
return 0;
}Output Example:
Solved Sudoku:
5 3 4 6 7 8 9 1 2
6 7 2 1 9 5 3 4 8
1 9 8 3 4 2 5 6 7
8 5 9 7 6 1 4 2 3
4 2 6 8 5 3 7 9 1
7 1 3 9 2 4 8 5 6
9 6 1 5 3 7 2 8 4
2 8 7 4 1 9 6 3 5
3 4 5 2 8 6 1 7 92. Hamiltonian Path - Backtracking
Hamiltonian Path হলো এমন একটি পথ যা গ্রাফের প্রতিটি শীর্ষে একবার করে পরিদর্শন করে। Hamiltonian Cycle যদি শেষ শীর্ষে গিয়ে আবার প্রথম শীর্ষে ফিরে আসে, তবে এটি একটি সাইকেল হয়। Hamiltonian Path এর সমস্যায় একটি গ্রাফে এমন একটি পথ খুঁজতে হয় যা প্রতিটি শীর্ষে একবার এবং একমাত্র একবার যায়।
Hamiltonian Path - Backtracking ইমপ্লিমেন্টেশন (সি প্রোগ্রামিং):
#include <stdio.h>
#include <stdbool.h>
#define V 5 // Number of vertices in graph
// Check if current vertex can be added to the path
bool isSafe(int graph[V][V], int path[], int pos, int v) {
// Check if this vertex is an adjacent vertex of the last vertex in path
if (graph[path[pos - 1]][v] == 0) {
return false;
}
// Check if vertex v is already in the path
for (int i = 0; i < pos; i++) {
if (path[i] == v) {
return false;
}
}
return true;
}
// Function to solve the Hamiltonian Path problem using backtracking
bool hamCycleUtil(int graph[V][V], int path[], int pos) {
// If all vertices are included in the path, return true
if (pos == V) {
return true;
}
// Try different vertices as the next candidate in the path
for (int v = 1; v < V; v++) {
if (isSafe(graph, path, pos, v)) {
path[pos] = v;
// Recur to construct the rest of the path
if (hamCycleUtil(graph, path, pos + 1)) {
return true;
}
// Backtrack
path[pos] = -1;
}
}
return false;
}
// Function to solve the Hamiltonian Path problem
bool hamCycle(int graph[V][V]) {
int path[V];
// Initialize the path
for (int i = 0; i < V; i++) {
path[i] = -1;
}
// Start from vertex 0
path[0] = 0;
if (hamCycleUtil(graph, path, 1)) {
printf("Hamiltonian Path: ");
for (int i = 0; i < V; i++) {
printf("%d ", path[i]);
}
printf("\n");
return true;
}
printf("No Hamiltonian Path exists\n");
return false;
}
int main() {
// Example graph (adjacency matrix)
int graph[V][V] = {
{0, 1, 0, 1, 0},
{1, 0, 1, 1, 1},
{0, 1, 0, 1, 0},
{1, 1, 1, 0, 1},
{0, 1, 0, 1, 0}
};
if (!hamCycle(graph)) {
printf("No Hamiltonian Path exists\n");
}
return 0;
}Output Example:
Hamiltonian Path: 0 1 2 3 4**স
ারসংক্ষেপ**
- Sudoku Solver: Backtracking ব্যবহার করে একটি Sudoku পাজল সমাধান করা সম্ভব। এটি খুঁজে বের করে একটি সংখ্যার জন্য বৈধ স্থানে স্থানান্তর করার সম্ভাব্যতা পরীক্ষা করে এবং যদি কোনো স্থানে সংখ্যার পুনরাবৃত্তি থাকে, তবে তা ফিরে আসে এবং পরবর্তী বিকল্প পরীক্ষা করে।
- Hamiltonian Path: Backtracking ব্যবহার করে একটি গ্রাফের মধ্যে এমন একটি পথ খুঁজে বের করা যায় যা প্রতিটি শীর্ষ একবার করে পরিদর্শন করে। যদি কোনো পাথ পাওয়া না যায়, তবে এটি ব্যাকট্র্যাক করে এবং পরবর্তী সম্ভাব্য পাথ পরীক্ষা করে।
Backtracking এর মূল উদ্দেশ্য হলো সমস্যার সকল সম্ভাব্য সমাধান খোঁজা, এবং যদি কোনো সমাধান ভুল হয়, তবে তা বাদ দিয়ে পরবর্তী সমাধানে যাওয়ার জন্য পুনরাবৃত্তি করা।
Read more
